#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,a[N],lst[N],vis[N];
#define ll long long
struct Tree{
	int tag,mi,cnt;
}t[1<<18];
#define mid ((l+r)>>1)
void build(int p,int l,int r){
	t[p].tag=t[p].mi=0;
	t[p].cnt=r-l+1;
	if(l<r){
		build(2*p,l,mid),build(2*p+1,mid+1,r);
	}
}
void change(int p,int l,int r,int lt,int rt,int v){
	if(lt<=l&&r<=rt){
		t[p].tag+=v,t[p].mi+=v;
		return;
	}
	if(lt<=mid) change(2*p,l,mid,lt,rt,v);
	if(mid<rt) change(2*p+1,mid+1,r,lt,rt,v);
	t[p].mi=min(t[2*p].mi,t[2*p+1].mi);
	t[p].cnt=(t[2*p].mi==t[p].mi?t[2*p].cnt:0)+(t[2*p+1].mi==t[p].mi?t[2*p+1].cnt:0);
	t[p].mi+=t[p].tag;
}
inline ll solve(int S){
	build(1,1,n);
	ll ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1,x=i;j<=k+1&&x;++j,x=lst[x]){
			int v=(((S>>j)&1)?1:0)-(((S>>(j-1))&1)?1:0);
			if(v) change(1,1,n,lst[x]+1,x,v);
		}
		if(t[1].mi==0) ans+=t[1].cnt-(n-i);
	}
	return ans;
}
int main(){
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;++i) cin>>a[i],lst[i]=vis[a[i]],vis[a[i]]=i;
	ll ans=0;
	for(int z=0;z<(1<<k);++z) ans+=solve(z<<1)*(__builtin_popcount(z)%2==0?1:-1);
	cout<<ans;
	return 0;
}


